package com.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 3375. 使数组的值全部为 K 的最少操作次数
 * 给你一个整数数组 nums 和一个整数 k 。
 * 如果一个数组中所有 严格大于 h 的整数值都 相等 ，那么我们称整数 h 是 合法的 。
 * 比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个 合法 整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是 合法 整数。
 * 你可以对 nums 执行以下操作：
 * 选择一个整数 h ，它对于 当前 nums 中的值是合法的。
 * 对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。
 * 你的目标是将 nums 中的所有元素都变为 k ，请你返回 最少 操作次数。如果无法将所有元素都变 k ，那么返回 -1 。
 */
public class LeetCode3375 {

    public static void main(String[] arg0) {
        int[] nums = {9, 6, 5, 3};
        int k = 7;

        // 答案只可能是 -1，数组长度，数组长度-1 这三个值。
        int res = cal(nums, k);

        System.out.println("res: " + res);
    }

    public static int cal(int[] nums, int k) {
        Set<Integer> st = new HashSet<>();
        for (int num : nums) {
            if (k > num) {
                return -1;
            }
            if (k < num) {
                st.add(num);
            }
        }
        return st.size();
    }

    public static int dfs(int startIndex, int endIndex, int k, int nums[]) {
        int middle = (startIndex + endIndex) / 2;
        if (nums[middle] == k || (nums[middle] < k && nums[middle + 1] > k)) {
            return middle;
        }

        if (nums[middle] > k) {
            return dfs(startIndex, middle, k, nums);
        } else {
            return dfs(middle + 1, endIndex, k, nums);
        }
    }

}
